Erdős–Turán conjecture on additive bases

The Erdős–Turán conjecture is an old unsolved problem in additive number theory (not to be confused with Erdős conjecture on arithmetic progressions) posed by Paul Erdős and Pál Turán in 1941.

History

The conjecture was made jointly by Paul Erdős and Pál Turán in.^[1] In the original paper, they state

"(2) If $f(n) > 0$ for $n > n_0$ , then $\overline{\lim_{n \rightarrow \infty}} f(n) = \infty$ "

Here the function $f(n)$ refers to the additive representation function of a given subset of the natural numbers, $B$ . In particular, $f(n)$ is equal to the number of ways one can write the natural number $n$ as the sum of two (not necessarily distinct) elements of $B$ . If $f(n)$ is always positive for sufficiently large $n$ , then $B$ is called an additive basis (of order 2).^[2] This problem has attracted significant attention,^[2] but remains unsolved.

Progress

While the conjecture remains unsolved, there have been significant advance on the problem. First, we express the problem in modern language. For a given subset $B \subset \mathbb{N}$ , we define its representation function $r_B(n) = \#\{(a_1, a_2) \in B^2 | a_1 %2B a_2 = n \}$ . Then the conjecture states that if $r_B(n) > 0$ for all $n$ sufficiently large, then $\limsup_{n \rightarrow \infty} r_B(n) = \infty$ .

More generally, for any $h \in \mathbb{N}$ and subset $B \subset \mathbb{N}$ , we can define the $h$ representation function as $r_{B,h}(n) = \#\{(a_1, \cdots, a_h) \in B^h | a_1 %2B \cdots %2B a_h = n \}$ . We say that $B$ is an additive basis of order $h$ if $r_{B,h}(n) > 0$ for all $n$ sufficiently large. One can see from an elementary argument that if $B$ is an additive basis of order $h$ , then

$\displaystyle n \leq \sum_{m=1}^n r_{B,h}(m) \leq |B \cap [1,n]|^h$

So we obtain the lower bound $n^{1/h} \leq |B \cap [1,n]|$ .

The original conjecture spawned as Erdős and Turán sought a partial answer to Sidon's problem (see: Sidon sequence). Later, Erdős set out to answer the following question posed by Sidon: how close to the lower bound $|B \cap [1,n]| \geq n^{1/h}$ can an additive basis $B$ of order $h$ get? This question was answered positively in the case $h=2$ by Erdős in 1956.^[3] Erdős proved that there exists an additive basis $B$ of order 2 and constants $c_1, c_2 > 0$ such that $c_1 \log n \leq r_B(n) \leq c_2 \log n$ for all $n$ sufficiently large. In particular, this implies that there exists an additive basis $B$ such that $r_B(n) = n^{1/2 %2B o(1)}$ , which is essentially best possible. This motivated Erdős to make the following conjecture

If $B$ is an additive basis of order $h$ , then $\limsup_{n \rightarrow \infty} r_B(n)/\log n > 0.$

In 1986, Eduard Wirsing proved that a large class of additive bases, including the prime numbers, contains a subset that is an additive basis but significantly thinner than the original.^[4] In 1990, Erdős and Tetalli extended Erdős's 1956 result to bases of arbitrary order.^[5] In 2000, V. Vu proved that thin subbases exist in the Waring bases using the Hardy–Littlewood circle method and his polynomial concentration results.^[6] In 2006, Borwein, Choi, and Chu proved that for all additive bases $B$ , $f(n)$ eventually exceeds 7.^[7]

References

^ Erdős, Paul.; Turán, Pál (1941). "On a problem of Sidon in additive number theory, and on some related problems". Journal of the London Mathematical Society 16: 212–216. doi:10.1112/jlms/s1-16.4.212.
^ ^a ^b Tao, T.; Vu, V. (2006). Additive Combinatorics. New York: Cambridge University Press. p. 13. ISBN 0521853869.
^ Erdős, P. (1956). "Problems and results in additive number theory". Colloque sur le Theorie des Nombres: 127–137.
^ Wirsing, Eduard (1986). "Thin subbases". Analysis 6: 285–308.
^ Erdős, Paul.; Tetalli, Prasad (1990). "Representations of integers as the sum of $k$ terms". Random Structures Algorithms 1 (3): 245–261. doi:10.1002/rsa.3240010302.
^ Vu, Van (2000). "On a refinement of Waring's problem". Duke Mathematical Journal 105 (1): 107–134. doi:10.1215/S0012-7094-00-10516-9.
^ Borwein, Peter; Choi, Stephen; Chu, Frank (2006). "An old conjecture of Erdős–Turán on additive bases". Mathematics of Computation 75: 475–484.